【Leetcode】【python】Climbing Stairs 爬楼梯

发表于 2019-08-01 更新于 2021-08-22 分类于旧文归档阅读次数： Valine：

题目大意

一共有n级楼梯，每次能够爬一级或两级，共有多少种不同的爬法爬到顶端。注意：第一级楼梯也要上，也就是说第二个楼梯就有两种走法。

解题思路

动态规划，状态转移方程式：

1	dp[i] = dp[i-1]+dp[i-2]

代码

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 2:
            return n
        dp = [1 for __ in range(n)]  # 1,2,3,5,8
        dp[1] = 2
        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]

总结